// BalancingBST.cpp : Defines the entry point for the console application.

#include "stdafx.h"
#include <iostream>
#include <stack>
#include <queue>
#include <deque>
using namespace std;

#define null 0
struct TreeNode
{
    int value;
    TreeNode *left, *right;

    TreeNode() { };

    TreeNode(int v)
    {
        value=v;
        left=right=null;
    };
};


// Given an integer array, build a balanced BST. (minimum height)
//
// Recursion
// Algorithm:
//   1. Sort the integer array
//   2. Use binary search to build the BST in pre-order
// Analysis:
//   Time Complexity: O(nlogn)
//   Space Complexity: O(logn)
TreeNode *Array2BST(int *p, int left, int right)
{
    if(right<left) return null;

    int mid=left+(right-left)/2;
    TreeNode *node=new TreeNode(p[mid]);
    node->left=Array2BST(p,left,mid-1);
    node->right=Array2BST(p,mid+1,right);

    return node;
}

TreeNode *Array2BST(int *p, int n)
{
    if(!p||n<=0) return null;

    //MergeSort(p,n); // or HeapSort(p,n);
    return Array2BST(p,0,n-1);
}


// Iteration
// Algorithm:
//   1. Use 2 stacks, 1 for node, 1 for integers
//   2. Using binary search (left,mid,right) to create and push a node to node stack
//   3. Push left, mid, right to integer stack
// Analysis:
//   Time Complexity: O(nlogn)
//   Space Complexity: O(logn)
TreeNode *Array2BST_Iterative(int *p, int n)
{
    if(!p||n<=0) return null;

    int left=0,right=n-1,mid=left+(right-left)/2;

    stack<TreeNode *> s1;
    TreeNode *root=new TreeNode(p[mid]);
    s1.push(root);

    stack<int> s2;
    s2.push(left);
    s2.push(mid);
    s2.push(right);

    while(!s1.empty())
    {
        TreeNode *node=s1.top();
        s1.pop();

        int rRight=s2.top();
        s2.pop();
        int rLeft=s2.top()+1;

        int lRight=s2.top()-1;
        s2.pop();
        int lLeft=s2.top();
        s2.pop();

        if(rLeft<=rRight)
        {
            int m=rLeft+(rRight-rLeft)/2;
            node->right=new TreeNode(p[m]);
            s1.push(node->right);
            s2.push(rLeft);
            s2.push(m);
            s2.push(rRight);
        }

        if(lLeft<=lRight)
        {
            int m=lLeft+(lRight-lLeft)/2;
            node->left=new TreeNode(p[m]);
            s1.push(node->left);
            s2.push(lLeft);
            s2.push(m);
            s2.push(lRight);
        }
    }

    return root;
}


// Merge two BSTs to a single balanced BST.
// Algorithm: 1. Count the total number of nodes on the two BSTs.
//            2. Build a sorted array
//            3. Convert a sorted array to BST
// Analysis:
//   Time Complexity: O(m+n)
//   Space Complexity: O(m+n)
int CountTreeNodes(TreeNode *root)
{
    if(!root) return 0;
    return CountTreeNodes(root->left) + CountTreeNodes(root->right) + 1;
}
//O(n)

// In-Order traversal
void BST2Array(TreeNode *root, int *orgArray, int &pos)
{
    if(!root) return;

    BST2Array(root->left,orgArray,pos);
    orgArray[pos++]=root->value;
    BST2Array(root->right,orgArray,pos);
}
//O(n)

void BuildSortedArray(TreeNode *root1, int m, TreeNode *root2, int n, int *array)
{
    int *p=new int[m];
    int *q=new int[n];
    int s=0,t=0;
    BST2Array(root1,p,s);
    BST2Array(root2,q,t);

    int i=0,j=0,pos=0;
    while(i<m||j<n)
    {
        if(i<m&&j<n)
        {
            array[pos++]=p[i]<q[j] ? p[i++]:q[j++];
        }
        else if(i>=m&&j<n)
        {
            while(j<n)
            {
                array[pos++]=q[j++];
            }
        }
        else if(i<m&&j>=n)
        {
            while(i<m)
            {
                array[pos++]=p[i++];
            }
        }
    }

    delete []p;
    delete []q;
    return;
}
//O(m+n)

TreeNode *MergeBSTs(TreeNode *root1, TreeNode *root2)
{
    if(!root1) return root2;
    if(!root2) return root1;

    int m=CountTreeNodes(root1);
    int n=CountTreeNodes(root2);
    int *p=new int[m+n];

    BuildSortedArray(root1,m,root2,n,p);

    //check if the array can be built to a BST
    for(int i=0;i<m+n-1;i++)
    {
        if(p[i]==p[i+1])
        {
            delete[] p;
            return null;
        }
    }

    TreeNode *root=Array2BST(p, 0, m+n-1);
    delete[] p;

    return root;
}

int _tmain(int argc, _TCHAR* argv[])
{
    return 0;
}